Dijkstra's Algorithm Algorithm
Dijkstra's Algorithm is a renowned graph search algorithm developed by the Dutch computer scientist Edsger W. Dijkstra in 1956. It is designed to find the shortest path between a starting node (or vertex) and all other vertices in a weighted graph, where the weights represent distances, costs, or any other relevant metric. The algorithm operates on both directed and undirected graphs; however, it requires that the weights be non-negative, as negative weights can lead to incorrect results. Over the years, Dijkstra's Algorithm has become a crucial technique in various fields, including computer networks, transportation systems, and geographic information systems.
The algorithm works by iteratively selecting the unvisited vertex with the lowest known distance from the starting vertex, updating its distance if a shorter path is found, and marking it as visited. This process continues until all vertices have been visited or the shortest path to the target vertex has been determined. The implementation typically involves using a priority queue to efficiently select the unvisited vertex with the lowest distance at each step. The time complexity of Dijkstra's Algorithm depends on the data structures used and the graph's characteristics. With a binary heap as the priority queue, the algorithm has a time complexity of O(|V|^2), where |V| is the number of vertices. However, with more advanced data structures like Fibonacci heaps, the time complexity can be reduced to O(|V| + |E| log |V|), where |E| is the number of edges in the graph.
/*
Petar 'PetarV' Velickovic
Algorithm: Dijkstra's Algorithm
*/
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <complex>
#define MAX_N 100001
#define INF 987654321
using namespace std;
typedef long long lld;
int n;
struct Node
{
int dist;
vector<int> adj;
vector<int> weight;
};
Node graf[MAX_N];
bool mark[MAX_N];
struct pq_entry
{
int node, dist;
bool operator <(const pq_entry &a) const
{
if (dist != a.dist) return (dist > a.dist);
return (node > a.node);
}
};
//Dijkstrin algoritam za nalazenje duzina najkracih puteva iz jednog izvora u grafu
//Slozenost: O((V+E)log V)
inline void Dijkstra(int source)
{
priority_queue<pq_entry> pq;
pq_entry P;
for (int i=0;i<n;i++)
{
if (i == source)
{
graf[i].dist = 0;
P.node = i;
P.dist = 0;
pq.push(P);
}
else graf[i].dist = INF;
}
while (!pq.empty())
{
pq_entry curr = pq.top();
pq.pop();
int nod = curr.node;
int dis = curr.dist;
for (int i=0;i<graf[nod].adj.size();i++)
{
if (!mark[graf[nod].adj[i]])
{
int nextNode = graf[nod].adj[i];
if (dis + graf[nod].weight[i] < graf[nextNode].dist)
{
graf[nextNode].dist = dis + graf[nod].weight[i];
P.node = nextNode;
P.dist = graf[nextNode].dist;
pq.push(P);
}
}
}
mark[nod] = true;
}
}
int main()
{
n = 4;
graf[0].adj.push_back(1);
graf[0].weight.push_back(5);
graf[1].adj.push_back(0);
graf[1].weight.push_back(5);
graf[1].adj.push_back(2);
graf[1].weight.push_back(5);
graf[2].adj.push_back(1);
graf[2].weight.push_back(5);
graf[2].adj.push_back(3);
graf[2].weight.push_back(5);
graf[3].adj.push_back(2);
graf[3].weight.push_back(5);
graf[3].adj.push_back(1);
graf[3].weight.push_back(6);
graf[1].adj.push_back(3);
graf[1].weight.push_back(6);
Dijkstra(0);
printf("%d\n",graf[3].dist);
return 0;
}
